翻訳と辞書 Words near each other ・ "O" Is for Outlaw ・ "O"-Jung.Ban.Hap. ・ "Ode-to-Napoleon" hexachord ・ "Oh Yeah!" Live ・ "Our Contemporary" regional art exhibition (Leningrad, 1975) ・ "P" Is for Peril ・ "Pimpernel" Smith ・ "Polish death camp" controversy ・ "Pro knigi" ("About books") ・ "Prosopa" Greek Television Awards ・ "Pussy Cats" Starring the Walkmen ・ "Q" Is for Quarry ・ "R" Is for Ricochet ・ "R" The King (2016 film) ・ "Rags" Ragland ・ ! (album) ・ ! (disambiguation) ・ !! ・ !!! ・ !!! (album) ・ !!Destroy-Oh-Boy!! ・ !Action Pact! ・ !Arriba! La Pachanga ・ !Hero ・ !Hero (album) ・ !Kung language ・ !Oka Tokat ・ !PAUS3 ・ !T.O.O.H.! ・ !Women Art Revolution Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク LLL algorithm ： ウィキペディア英語版 Lenstra–Lenstra–Lovász lattice basis reduction algorithm The Lenstra–Lenstra–Lovász (LLL) lattice basis reduction algorithm is a polynomial time lattice reduction algorithm invented by Arjen Lenstra, Hendrik Lenstra and László Lovász in 1982. Given a basis $\backslash mathbf=\backslash \_2,\; \backslash dots,\; \backslash mathbf\_d\; \backslash \}$ with ''n''-dimensional integer coordinates, for a lattice L (a discrete subgroup of R''n'') with $\backslash \; d\; \backslash leq\; n$, the LLL algorithm calculates an ''LLL-reduced'' (short, nearly orthogonal) lattice basis in time :$O(d^5n\backslash log^3\; B)\backslash ,$ where B is the largest length of $b\_i$ under the Euclidean norm. The original applications were to give polynomial-time algorithms for factorizing polynomials with rational coefficients, for finding simultaneous rational approximations to real numbers, and for solving the integer linear programming problem in fixed dimensions. ==LLL reduction== The precise definition of LLL-reduced is as follows: Given a basis :$\backslash mathbf=\backslash \_1,\; \backslash dots,\; \backslash mathbf\_n\; \backslash \},$ define its Gram–Schmidt process orthogonal basis :$\backslash mathbf^$ *=\^ *_1, \dots, \mathbf^ *_n \}, and the Gram-Schmidt coefficients :$\backslash mu\_=\backslash frac^$ *_j\rangle}^ *_j\rangle}, for any . Then the basis $B$ is LLL-reduced if there exists a parameter $\backslash delta$ in (0.25,1] such that the following holds: # (size-reduced) For . By definition, this property guarantees the length reduction of the ordered basis. # (Lovász condition) For k = 1,2,..,n $\backslash colon\; \backslash delta\; \backslash Vert\; \backslash mathbf^$ *_\Vert^2 \leq \Vert \mathbf^ *_k\Vert^2+ \mu_^2\Vert \mathbf^ *_\Vert^2. Here, estimating the value of the $\backslash delta$ parameter, we can conclude how well the basis is reduced. Greater values of $\backslash delta$ lead to stronger reductions of the basis. Initially, A. Lenstra, H. Lenstra and L. Lovász demonstrated the LLL-reduction algorithm for $\backslash delta\; =\; \backslash frac$. Note that although LLL-reduction is well-defined for $\backslash delta\; =\; 1$, the polynomial-time complexity is guaranteed only for $\backslash delta$ in (0.25,1). The LLL algorithm computes LLL-reduced bases. There is no known efficient algorithm to compute a basis in which the basis vectors are as short as possible for lattices of dimensions greater than 4. However, an LLL-reduced basis is nearly as short as possible, in the sense that there are absolute bounds $c\_i\; >\; 1$ such that the first basis vector is no more than $c\_1$ times as long as a shortest vector in the lattice, the second basis vector is likewise within $c\_2$ of the second successive minimum, and so on. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Lenstra–Lenstra–Lovász lattice basis reduction algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.